package com.structure.tree.binaryTree;

import java.util.Stack;

public class BinaryTree {

	private BinaryTreeNode root;
	
	
	public BinaryTree(){
		root = new BinaryTreeNode(1,"A");
	}
	
	/**
	 * 创建一个二叉树 
	 *    A
	 * B     C
	 *D E   F  G
	 *     H I  J
	 * 前序遍历（先根遍历）：ABDECF
	 */
	public void createBinaryTree(){
		BinaryTreeNode nodeB = new BinaryTreeNode(2,"B");
		BinaryTreeNode nodeC = new BinaryTreeNode(2,"C");
		BinaryTreeNode nodeD = new BinaryTreeNode(3,"D");
		BinaryTreeNode nodeE = new BinaryTreeNode(3,"E");
		BinaryTreeNode nodeF = new BinaryTreeNode(3,"F");
		BinaryTreeNode nodeG = new BinaryTreeNode(3,"G");
		BinaryTreeNode nodeH = new BinaryTreeNode(4,"H");
		BinaryTreeNode nodeI = new BinaryTreeNode(4,"I");
		BinaryTreeNode nodeJ = new BinaryTreeNode(4,"J");
		root.setLeftTreeNode(nodeB);
		root.setRightTreeNode(nodeC);
		nodeB.setLeftTreeNode(nodeD);
		nodeB.setRightTreeNode(nodeE);
		nodeC.setLeftTreeNode(nodeF);
		
	}
	
	public int getTreeHight(){
		
		return this.hight(root);
	}
	
	/**
	 * 前序遍历（先根遍历）
	 */
	public void preSearch(BinaryTreeNode node){
		if(node!=null){
			System.out.println(node.getKey()+":"+node.getData());
			preSearch(node.getLeftTreeNode());
			preSearch(node.getRightTreeNode());
		}

	}
	
	/**
	 * 非递归形式的 前根序遍历。
	 * @param node
	 */
	public void noRecurPreSearch(BinaryTreeNode node){
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		while(node!=null || stack.size()>0){
			while(node!=null){
				System.out.println(node.getKey()+":"+node.getData());
				stack.push(node);
				node = node.getLeftTreeNode();
			}
			while(stack.size()>0){
				node = stack.pop();
				node = node.getRightTreeNode();

			}
		}


	}
	
	/**
	 * 中根序遍历
	 * @param node
	 */
	public void inSearch(BinaryTreeNode node){
		if(node!=null){
			inSearch(node.getLeftTreeNode());
			System.out.println(node.getKey()+":"+node.getData());
			inSearch(node.getRightTreeNode());
		}
	}
	
	/**
	 * 后根序遍历
	 * @param node
	 */
	public void postSearch(BinaryTreeNode node){
		if(node!=null){
			postSearch(node.getLeftTreeNode());
			postSearch(node.getRightTreeNode());
			System.out.println(node.getKey()+":"+node.getData());
		}
	}
	
	
	private boolean isHasChild(BinaryTreeNode node){
		if(node.getLeftTreeNode()==null&&node.getRightTreeNode()==null)
			return false;
		else
			return true;
	}
	
	
	
	private int hight(BinaryTreeNode node){
		if(node==null){
			return 0;
		}else{
			int left = hight(node.getLeftTreeNode());
			int right = hight(node.getRightTreeNode());

			System.out.println(left+":"+right);
		}
		return 0;
	}
	
	
	public static void main(String[] args){
		BinaryTree tree = new BinaryTree();
		tree.createBinaryTree();
		
//		tree.preSearch(tree.root);
//		tree.inSearch(tree.root);
//		tree.postSearch(tree.root);
		tree.noRecurPreSearch(tree.root);
	}
	
}
